// 快速排序
// 选择最左边的值为主元(基准值)
// 这是选完基值之后，选出剩余大于基值的元素 和小于基值的元素
// 再重新排序
// function quicksort(arr) {
//   if (arr.length < 2) {
//     return arr
//   } else {
//     let pivot = arr[0];
//     let less = arr.slice(1).filter(function(value, index) {
//       return value <= pivot;
//     })
//     let greater = arr.slice(1).filter(function(value, index) {
//       return value > pivot;
//     })

//     return [...quicksort(less), pivot, ...quicksort(greater)];
//   }
// }

// function quickSort(arr) {
//   if (arr.length <= 1) {
//     return arr;
//   }
//   let pivot = arr[0];
//   const left = [];
//   const right = [];
//   for (let i = 1; i < arr.length; i++) {
//     if (arr[i] < pivot) {
//       left.push(arr[i]);
//     } else {
//       right.push(arr[i]);
//     }
//   }
//   return quickSort(left).concat(pivot, quickSort(right))
// }

// function quickSort2(arr, l, r) {
//   //递归出口
//   if (l >= r)
//     return;
//   var i = l; // 左指针
//   var j = r; // 右指针
//   var pivot = arr[l]; //基准数，这里取数组第一个数
//   //左右指针相遇的时候退出扫描循环
//   while (i < j) {
//     //右指针从右向左扫描，碰到第一个小于基准数的时候停住
//     while (i < j && arr[j] >= pivot)
//       j--;
//     //左指针从左向右扫描，碰到第一个大于基准数的时候停住
//     while (i < j && arr[i] <= pivot)
//       i++;
//     //交换左右指针所停位置的数
//     [arr[i], arr[j]] = [arr[j], arr[i]];
//   }
//   //最后交换基准数与指针相遇位置的数
//   [arr[l], arr[i]] = [arr[i], arr[l]];
//   //递归处理左右数组
//   quickSort2(arr, l, i - 1);
//   quickSort2(arr, i + 1, r);
//   return arr;
// }

// 快速排序 对于几乎已经有序的序列来说 基准值取左边的数不是一个好的方法
// 好的方法就是选择中间的数或通过 Math.random()来随机选取一个数。
function quickSort3(arr, l, r) {
  if (l >= r) {
    return;
  }
  let i = l, j = r;
  // 先求出随机数索引
  // let randomIndex = Math.floor(Math.random() * (r - l + 1) + l);
  // 或者求出中间数 
  let Index = Math.floor((l + r) / 2);
  // 随机数(中间数)与待排数组的第一个数交换
  [arr[Index], arr[l]] = [arr[l], arr[Index]];
  // 此时基准值就变成了第一个数
  let pivot = arr[l];
  while (i < j) {
    while (i < j && arr[j] >= pivot) {
      j--;
    }
    while (i < j && arr[i] <= pivot) {
      i++;
    }
    [arr[i], arr[j]] = [arr[j], arr[i]];
  }
  [arr[i], arr[l]] = [arr[l], arr[i]];
  quickSort3(arr, l, i - 1);
  quickSort3(arr, i + 1, r);
  return arr;
}

function quickSort(arr) {
  // return quickSort2(arr, 0, arr.length - 1);
  return quickSort3(arr, 0, arr.length - 1);
}

// 测试用例
// const arr = [5, 4, 3, 2, 1];
const arr = [24, 17, 31];
// console.log(quicksort(arr))
console.log(quickSort(arr));
// console.log(quickSort(arr));